import random
import math


# 计算两个点之间的欧氏距离
def euclidean_distance(x1, x2):
    return math.sqrt(sum((x1[i] - x2[i]) ** 2 for i in range(len(x1))))


# 初始化质心，随机从数据中选择k个点
def initialize_centroids(data, k):
    return random.sample(data, k)


# 为每个数据点分配簇
def assign_cluster(x, centroids):
    min_distance = float('inf')
    cluster_index = -1
    for i, centroid in enumerate(centroids):
        distance = euclidean_distance(x, centroid)
        if distance < min_distance:
            min_distance = distance
            cluster_index = i
    return cluster_index


# 更新质心
def update_centroids(data, k, assignments):
    new_centroids = []
    for i in range(k):
        cluster_points = [data[j] for j in range(len(data)) if assignments[j] == i]
        if cluster_points:  # 计算簇内点的均值
            new_centroid = [sum(x) / len(x) for x in zip(*cluster_points)]
            new_centroids.append(new_centroid)
        else:
            new_centroids.append(random.choice(data))  # 如果某个簇没有点，随机选择一个点作为质心
    return new_centroids


# K均值聚类主函数
def Kmeans(data, k, epsilon, iteration):
    # 初始化质心
    centroids = initialize_centroids(data, k)
    prev_centroids = centroids[:]

    # 迭代过程
    for it in range(iteration):
        assignments = [assign_cluster(x, centroids) for x in data]

        # 更新质心
        centroids = update_centroids(data, k, assignments)

        # 计算质心的变化
        centroid_shift = sum(euclidean_distance(prev_centroids[i], centroids[i]) for i in range(k))

        if centroid_shift < epsilon:
            print(f"Converged at iteration {it + 1}")
            break

        prev_centroids = centroids[:]

    return centroids, assignments


# 示例数据
data = [
    [1.0, 2.0], [1.5, 1.8], [5.0, 8.0], [8.0, 8.0], [1.0, 0.6], [9.0, 11.0],
    [8.0, 2.0], [10.0, 2.0], [9.0, 3.0]
]

# 运行K均值算法
k = 3
epsilon = 0.01
iteration = 100

centroids, assignments = Kmeans(data, k, epsilon, iteration)

# 输出最终结果
print("最终质心：")
for i, centroid in enumerate(centroids):
    print(f"簇 {i}: {centroid}")

print("\n每个点的簇分配：")
for i, assignment in enumerate(assignments):
    print(f"点 {data[i]} 被分配到簇 {assignment}")
